package com.wuyou.dataStructure.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 路径总和：
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。
 * 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum。
 * 如果存在，返回 true ；否则，返回 false 。
 */
public class HasPathSum {


    public boolean sol_3(TreeNode root, int targetSum) {

        return help(root, targetSum,0);
    }

    public boolean help(TreeNode root, int targetSum, int curSum) {
        if (root == null) {
            return false;
        }
        curSum+=root.val;
        if (root.left == null && root.right == null) {
            return targetSum == curSum;
        }
        return help(root.left, targetSum, curSum) || help(root.right, targetSum, curSum);
    }
    public boolean sol_1(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        byte[] result = {0};
        dfs(root, targetSum,0, result);
        return result[0] == 1;
    }

    public void dfs(TreeNode root, int targetSum, int curSum, byte[] result) {
        if (root == null) {
            return;
        }
        dfs(root.left, targetSum, curSum + root.val, result);
        dfs(root.right, targetSum, curSum + root.val, result);
        if (root.left == null && root.right == null && result[0]!=1) {
            result[0] = (byte) ((targetSum == curSum + root.val) ? 1 : 0);
        }
    }
    public boolean sol_2(TreeNode root, int targetSum) {
        return hasPathSumHelper(root, 0, targetSum);
    }

    public boolean hasPathSumHelper(TreeNode root, int a, int targetSum) {
        // 节点为null直接返回false
        if(root == null) return false;
        //累加节点值
        a += root.val;
        // 到叶子节点值相等则返回false
        // 也可以改成
        //if(root.left == null && root.right == null) return a == targetSum;
        if(root.left == null && root.right == null && a == targetSum) return true;
        //递归遍历左子树右子树
        return hasPathSumHelper(root.left, a, targetSum) || hasPathSumHelper(root.right, a, targetSum);
    }
}
